class Solution:
    def wordBreak(self, s: str, wordDict) -> bool:
        if s is None or len(s) == 0:
            return True
        wordDict = set(wordDict)

        matching = set()
        matching.add(0)
        for i in range(len(s)):
            for matchIndex in matching:
                if s[matchIndex:i + 1] in wordDict:
                    matching.add(i + 1)
                    break

        return True if len(s) in matching else False


if __name__ == '__main__':
    so = Solution()
    s = "leetcode"
    wordDict = ["leet", "code"]

    re = so.wordBreak(s, wordDict)
    print(re)
